One of the most important considerations for handling network traffic is packet throughput. Network processors and the like are designed to efficiently process very large numbers of packets per second. In order to process a packet, the network processor (and/or network equipment employing the network processor) needs to extract data from the packet header indicating the destination of the packet, class of service, etc., store the payload data in memory, perform various overhead functions, enqueue and dequeue the payload data, etc.
In general, the amount of time it takes to process a packet is much greater than the line-rate at which packets are received. For example, the OC192 line rate corresponds to a 10 Gigabit/second throughput. If the average packet size is 49 bytes, this corresponds to a packet receive rate of approximately 25 million packets/second, or one packet every 40 nanoseconds. Meanwhile, packet processing typically takes several thousand processor cycles to perform. For instance, a high-performance network processor running at 1.4 GHz that requires 3000 cycles per packet would take 2142 nanoseconds to process each packet.
In order to maintain line-rate throughput levels, packet-processing operations need to be performed in a predictable manner. A typical scheme employs various mechanisms for “hiding” processing latencies. For example, if approximately the same number of cycles are used to processes each packet, the specific amount of processing latency is somewhat immaterial—the processing latency just appears as a delay, but does not reduce the line-rate throughput. In contrast, if substantially different amounts of processing latency are encountered, the throughput will fall below line-rate unless some mechanism is employed to handle packets with longer processing latencies. Under a typical scenario, line-rate throughput is maintained by simply dropping significant numbers of packets. This is highly undesirable, and clearly reduces the “real” throughput of the network.
Among other operations, the foregoing packet processing operations require multiple memory accesses. One or (generally) more of these memory accesses relate to determining the “next hop” for the packet. The next hop represents the next network element (e.g., router, switch, etc.) to which the packet is to be forwarded. Typically, a forwarding information base (FIB) or the like is used to determine the next hop based on the destination address (and possibly other information) for the packet. To speed up this process, various indexing schemes are used. However, the amount of latency encountered during the performance of conventional indexing schemes is not predictable under many circumstances.